package practice6;

import java.util.Arrays;
import java.util.Scanner;

public class P2695 {
    static int n,m;
    static int INF=(int)1e9;
    static int[] dist=new int[1010];	//表示从起点到各个城市的时间(加上停留时间)
    static int[] stay=new int[1010];	//表示各个城市的停留于时间
    static int[][] g=new int[1010][1010];	//有向带权图
    static boolean[] st=new boolean[1010];	//该城市是否访问过

    //初始化带权图
    public static void initGraph() {
        for(int i=0;i<1010;i++) {
            Arrays.fill(g[i], INF);
        }
    }

    //Dijkstra求最短路径
    public static int dijkstra() {
        Arrays.fill(dist,INF);
        dist[1]=0;
        for(int i=0;i<n-1;i++) {
            //找出离起点最近的点
            int t=-1;
            for(int j=1;j<=n;j++) {
                if(!st[j] && (t==-1 || dist[j]<dist[t])) {
                    t=j;
                }
            }
            st[t]=true;
            //更新其邻居的值
            for(int j=1;j<=n;j++) {
                if(g[t][j]!=INF) {
                    dist[j]=Math.min(dist[j], dist[t]+g[t][j]);
                }
            }
        }
        if(dist[n]==INF) {
            return -1;
        }
        return dist[n]-stay[n];
    }

    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        n=sc.nextInt();		//城市数量
        m=sc.nextInt();		//路线数量
        initGraph();
        for(int i=1;i<=n;i++) {
            stay[i]=sc.nextInt();
        }
        for(int i=0;i<m;i++) {
            int u=sc.nextInt();
            int v=sc.nextInt();
            int c=sc.nextInt();
            g[u][v]=c+stay[v];
            g[v][u]=c+stay[u];
        }
        int ans=dijkstra();
        System.out.println(ans);

    }

}
